<?php
/**
 * @title 33. 搜索旋转排序数组 - 二分
 * @author start2004
 */

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function search($nums, $target) {
        $left = 0;
        $right = count($nums)-1;

        /**
         * @since 2020-07-04 特殊情况先处理
         */
        if($right == -1){
            return -1;
        } else {}

        /**
         * @since 2020-07-04 找到升序列, 先排查
         *          mid
         *           ↓
         *    4,5,6, 7, 9,0,2
         *    ↑             ↑
         * left             right
         */
        // echo "nums=[", implode(",", $nums) ,"], target={$target}", PHP_EOL;
        while($left<=$right){
            // $mid = intval(($left+$right)/2);
            $mid = ($left+$right)>>1;
            $midVal = $nums[$mid];
            $leftVal = $nums[$left];
            $rightVal = $nums[$right];
            // echo "[left, mid, right], [{$left}, {$mid}, {$right}], val = [{$leftVal}, {$midVal}, {$rightVal}]", PHP_EOL;

            /**
             * @since 2020-07-04 [left, mid], 升序
             */
            if($leftVal <= $midVal){
                // echo "[left, mid]=[{$leftVal}, {$midVal}], 升序, ";
                /**
                 * @since 2020-07-04 target在升序列
                 */
                if($target >= $leftVal AND $target <= $midVal){
                    // echo "target在升序",  PHP_EOL;
                    return self::find($nums, $left, $mid, $target);
                    break;
                } else {
                    // echo "target不在升序",  PHP_EOL;
                    $left = $mid+1;
                }
            } else {
                /**
                 * @since 2020-07-04 [mid, right], 升序
                 * @since 2020-07-04 target在升序列
                 */
                // echo "[mid, right]=[{$midVal}, {$rightVal}], 升序, ";
                if($target >= $midVal AND $target <= $rightVal){
                    // echo "target在升序",  PHP_EOL;
                    return self::find($nums, $mid, $right, $target);
                    break;
                } else {
                    // echo "target不在升序",  PHP_EOL;
                    $right = $mid-1;
                }
            }
        }

        /**
         * @return
         */
        return -1;
    }

    /**
     * @title 二分查找
     * @author start2004
     * @since 2020-07-21 Created
     *
     * @param array $nums
     * @param int $left
     * @param int $right
     * @param int $target
     */
    function find($nums = [], $left = 0, $right = 0, $target = 0){
        while($left <= $right){
            $mid = ($left+$right)>>1;
            $midVal = $nums[$mid];

            if($target == $midVal){
                return $mid;
                break;
            } elseif($target > $midVal) {
                $left = $mid+1;
            } else {
                $right = $mid-1;
            }
        }

        /**
         * @return
         */
        return -1;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.04_4.php
 */
$datas = [
    [[4,5,6,7,0,1,2], 0],
    [[4,5,6,7,0,1,2], 3],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->search($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
